(A) Field of the Invention
The invention relates to a quantum computer; that is, an array of quantum bits (called qubits). More specifically, it relates to methods for using a classical computer to generate a sequence of operations that can be used to operate a quantum computer. The invention also relates to methods for sampling a probability distribution and classical probabilistic networks (called classical Bayesian networks).
(B) Description of Related Art
Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.    Ref.BNets is http://en.wikipedia.org/wiki/Bayesian_network    Ref.GSamp is “Rapid Sampling Through Quantum Computing” by Lov Grover, ariv:quant-ph/9912001    Ref.GPat is “Fast Quantum Mechanical Algorithms”, U.S. Pat. No. 6,317,766, by Lov K. Grover    Ref.GWiki is http://en.wikipedia.org/wiki/Grover's_algorithm    Ref.TexasPat is “Quantum Circuit Design for Grover's Algorithm”, U.S. Pat. No. 7,028,275, by G. Chen, Z. Diao, M. Zubairy    Ref.Som is “Quantum Simulated Annealing” by R. Somma, S. Boixo, H. Barnum, arXiv:0712.1008    Ref.Woc is “Speed-up via Quantum Sampling” by Pawel Wocjan, Anura Abeyesinghe, arXiv:0804.4259    Ref.GPi/3 is “A Different Kind of Quantum Search” by Lov Grover, arXiv:quant-ph/0503205    Ref.TucQusann is “Code Generator for Quantum Simulated Annealing” by R. R. Tucci, arXiv:0908.1633    Ref.TucQuibbs1 is “Quantum Gibbs Sampling Using Szegedy Operators” by R. R. Tucci, arXiv:0910.1647    Ref.TucAfga is “An Adaptive, Fixed-Point Version of Grover's Algorithm” by R. R. Tucci, arXiv:1001.5200.    Ref.TucQuibbs2 is “Quibbs, a Code Generator for Quantum Gibbs Sampling” by R. R. Tucci, arXiv:1004.2205
This invention deals with quantum computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating those qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer follows a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs are often represented as quantum circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. One can find on the Internet many excellent expositions on quantum computing.
This invention also deals with sampling a probability distribution. Given a probability distribution Px( ) defined for all points x in some domain val(x), sampling Px( ) means obtaining a collection {x(1),x(2), . . . , x(Nsam)} of points in val(x) which are distributed according to Px( ). If one can obtain such a collection of points, one can use it to evaluate approximately the expected value of any function defined on val(x). Hence, sampling a probability distribution is very useful. If the points x∈val(x) have dim(x) components, and dim(x) is very high, then sampling Px( ) becomes very difficult. The reason is that the majority of the sample points x(j) will come from those regions of val(x) where Px( ) is high, but finding those regions requires that we explore the entire set val(x). When dim(x) is high, set val(x) is huge, because its volume grows exponentially with dim(x).
The preferred embodiment of this invention uses a Bayesian network to specify Px( ). Bayesian networks are described, for example, in Ref.BNets.
There are several standard techniques for sampling probability distributions using a classical computer (for instance, Monte Carlo techniques like Gibbs sampling and Metropolis-Hastings sampling). This invention differs from those standard techniques in that we propose using a quantum computer to generate the sample of points. This is an exciting possibility to the inventor Tucci for the following reasons. Quantum computers use quantum mechanics, which has probabilities built into it, so doing Monte Carlo tricks should come natural to a quantum computer. Furthermore, systems in a quantum mechanical state have a knack for being in many places at once, so one suspects that quantum computers can explore large spaces like val(x) much faster than classical computers can.
Grover in Ref.GSamp seems to have been the first to propose a method for sampling probability distributions using a quantum computer. Let us call his method GSamp for short. In a nutshell, GSamp applies the so called Grover's “search” Algorithm (the one discussed in Ref.GPat and Ref.GWiki) to NB+1 qubits, using the starting state|s′=|0NB|0and the target state
                                                                                                                                                          t                      〉                                        =                                                                  1                                                                              2                                                          N                              B                                                                                                                          ⁢                                              ∑                        x                                                                                                              ⁢                x                            〉                        ⊗                          (                                                                                          P                                              x                        _                                                              ⁡                                          (                      x                      )                                                                      |                0                            〉                                +                                    1              -                                                P                                      x                    _                                                  ⁡                                  (                  x                  )                                                                    ❘        1            〉        )    ,where the sum is over all x∈{0,1}NB. Once this starting state is driven into this target state, one measures the target state to sample Px(x). A serious defect of GSamp is that its target state is useless for sampling Px(x), because it has a vanishingly small amplitude of size O(1/√{square root over (2NB)}) for all x. The preferred embodiment of this invention, which we call Quibbs, does not suffer from this defect because its target state is
                                                                                                            t                  〉                                =                                                      ∑                    x                                    ⁢                                                                                    P                                                  x                          _                                                                    ⁡                                              (                        x                        )                                                                                                                                ⁢            x                    〉                ⊗            |      0        〉    .Thus, Quibbs' target state has a finite amplitude at those x for which Px(x) is finite.
Some previous patents (see Ref.GPat and Ref.TexasPat) use Grover's search algorithm, but they do not mention in their claims or specification its use for sampling a probability distribution.
Beside Ref.GSamp, Ref.Som and Ref.Woc have also given methods for sampling probability distributions with a quantum computer. Ref.Som uses the quantum Zeno effect, whereas Ref.Woc uses Grover's pi/3 algorithm (the one in Ref.GPi/3). The present invention uses neither the quantum Zeno effect, nor Grover's pi/3 algorithm. It uses more efficient techniques instead.
Ref.Som and Ref.Woc are both concerned with optimization (via simulated annealing) of a non-negative function E(x) defined for all x, whereas the present invention is concerned with sampling an arbitrary probability distribution Px(x). Even though optimization and sampling are related and share some common techniques, they are not the same thing. For instance, sampling allows you to find the expected value of any function of x, whereas optimization doesn't. Optimization allows you to find a good minimum of E(x) whereas sampling alone doesn't.
The inventor Tucci first published a description of this invention on Oct. 9, 2009, in Ref.TucQuibbs1. Later, he added further details in Ref.TucAfga and Ref.TucQuibbs2.